package com.wfs.suanfa.leet;

/**
 * 二分法查找例子
 * @author wfs
 * @date 2022-08-11 16:28
 */
public class LookupSuanFa {

    public static void main(String[] args) {
        int[] arr={1,3,4,5,6,8,8,8,11,18};
        System.err.println(bsearchRightOne(arr,arr.length,8));

    }


    /**
     * 二分法查找获取最小下标
     */
    public static int bsearch(int[] arr,int n,int value){
        int low=0;
        int high=n-1;
        while (low<high){
            int mid=low+((high-low)>>1);
            if (arr[mid]>value){
                high=mid-1;
            }else if (arr[mid]<value){
                low=mid+1;
            }else {
                if (mid==0 || arr[mid-1]!=value){
                    return mid;
                }
                high=mid-1;
            }

        }
        return -1;
    }

    /**
     *二分法查找获取最大下标
     */
    public static int bsearchMax(int[] arr,int n,int value){
        int low=0;
        int high=n-1;
        while (low<high){
            int mid=low+((high-low)>>1);
            if (arr[mid]>value){
                high=mid-1;
            }else if (arr[mid]<value){
                low=mid+1;
            }else {
                if (mid==(n-1) || arr[mid+1]!=value){
                    return mid;
                }
                low=mid+1;
            }

        }
        return -1;
    }

    /**
     * 查找第一个大于等于给定值的元素
     */
    public static int bsearchLeftOne(int[] arr,int n,int value){
        int low=0;
        int high=n-1;
        while (low<high){
            int mid=low+((high-low)>>1);
            if (arr[mid]>=value){
                if (mid==0 || arr[mid-1]<value){
                    return mid;
                }
                high=mid-1;
            }else {
                low=mid+1;
            }

        }
        return -1;
    }

    /**
     * 查找最后一个小于等于给定值的元素
     */
    public static int bsearchRightOne(int[] arr,int n,int value){
        int low=0;
        int high=n-1;
        while (low<high){
            int mid=low+((high-low)>>1);
            if (arr[mid]<=value){
                if (mid==(n-1) || arr[mid+1]>value){
                    return mid;
                }
                low=mid+1;
            }else {
                high=mid-1;
            }

        }
        return -1;
    }
}
